package DP.子序列;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import static MyUtils.MHUtils.*;
import static MyUtils.MHMoban.*;

/*
内部+1 M(f1+1, f2+1, f3+1)

总思路：子集

map优化：
    key=cI+"" , 不要+fa/step

for里面只能con
    不可return, for里return后面全丢了
 */
public class 最长递增子序列300_自回溯 {
    @Test
    public void test() {
        int[] p = {3,1,2,3,1};
        System.out.println(lengthOfLIS(p));
    }

    int[] p; int n;
    public int lengthOfLIS(int[] nums) {
        p=nums; n =nums.length;
        int cI=0,fa=-999;
        return bT(cI,fa);
    }
    private int bT(int cI, int fa) {
        if(cI==n){
            return 0;
        }

        int max = 0;
        for (int i = cI; i <n; i++) {
            //222不是递增,至少+1
            if(p[i] <= fa){
                //con就是不计入res (不要多想)
                continue;
            }
            //迭代i+1, fa为i
            int f = bT(i+1, p[i]) + 1;
            max = Math.max(f,max);
        }
        return max;
    }
}
